package 中等;

import java.util.HashMap;
import java.util.Map;

public class 字符串排列 {

    public static void main(String[] args) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        //"trinitrophenylmethylnitramine"
        //"dinitrophenylhydrazinetrinitrophenylmethylnitramine"
        String str = "dinitrophenylhydrazinetrinitrophenylmethylnitramine";
        String target  = "trinitrophenylmethylnitramine";
        System.out.println(checkInclusion(str,target ));
        //char c;
        //for (int i = 0; i < target.length(); i++) {
        //     c = target.charAt(i);
        //    need.put(c, need.getOrDefault(c,0 )+1);
        //}
        ////for (int i = 0; i < "dinitrophenylhydrazinetrinitr".length(); i++) {
        ////    c = "dinitrophenylhydrazinetrinitr".charAt(i);
        ////    window.put(c, window.getOrDefault(c,0 )+1);
        ////}
        ////System.out.println(" ");
        //
        //for (int i = 0; i < "trophenylhydrazinetrinitrophe".length(); i++) {
        //    c = "trophenylhydrazinetrinitrophe".charAt(i);
        //    window.put(c, window.getOrDefault(c,0 )+1);
        //}
        //System.out.println(" ");


    }

    public static boolean checkInclusion(String str, String target) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        char c;
        int length = str.length();
        for (int i = 0; i < target.length(); i++) {
            c = target.charAt(i);
            need.put(c, need.getOrDefault(c,0 )+1);
        }
        int left = 0;
        int right = 0;
        int valid = 0;
        while (right< length){
            c = str.charAt(right);
            right++;
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0 )+1 );
                if (window.get(c).intValue()==need.get(c).intValue()){
                    valid++;
                }
            }
            while (right-left==target.length()){
                if (valid == need.size()){
                    System.out.println(str.substring(left,right ));
                    return true;
                }
                c = str.charAt(left);
                left ++;
                if (need.containsKey(c)){
                    window.put(c,window.get(c)-1 );
                    if (window.get(c).intValue()==need.get(c).intValue()-1){
                        valid--;
                    }
                }

            }
        }
        return false;

    }
}
